package com.sheng.leetcode.year2023.month12.day21;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;

/**
 * @author by ls
 * @date 2023/12/21
 * <p>
 * 2866. 美丽塔 II<p>
 * <p>
 * 给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。<p>
 * 你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。<p>
 * 如果以下条件满足，我们称这些塔是 美丽 的：<p>
 * 1 <= heights[i] <= maxHeights[i]<p>
 * heights 是一个 山脉 数组。<p>
 * 如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山脉 数组：<p>
 * 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]<p>
 * 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]<p>
 * 请你返回满足 美丽塔 要求的方案中，高度和的最大值 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：maxHeights = [5,3,4,1,1]<p>
 * 输出：13<p>
 * 解释：和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：<p>
 * - 1 <= heights[i] <= maxHeights[i]<p>
 * - heights 是个山脉数组，峰值在 i = 0 处。<p>
 * 13 是所有美丽塔方案中的最大高度和。<p>
 * <p>
 * 示例 2：<p>
 * 输入：maxHeights = [6,5,3,9,2,7]<p>
 * 输出：22<p>
 * 解释： 和最大的美丽塔方案为 heights = [3,3,3,9,2,2] ，这是一个美丽塔方案，因为：<p>
 * - 1 <= heights[i] <= maxHeights[i]<p>
 * - heights 是个山脉数组，峰值在 i = 3 处。<p>
 * 22 是所有美丽塔方案中的最大高度和。<p>
 * <p>
 * 示例 3：<p>
 * 输入：maxHeights = [3,2,5,5,2,3]<p>
 * 输出：18<p>
 * 解释：和最大的美丽塔方案为 heights = [2,2,5,5,2,2] ，这是一个美丽塔方案，因为：<p>
 * - 1 <= heights[i] <= maxHeights[i]<p>
 * - heights 是个山脉数组，最大值在 i = 2 处。<p>
 * 注意，在这个方案中，i = 3 也是一个峰值。<p>
 * 18 是所有美丽塔方案中的最大高度和。<p>
 * <p>
 * 提示：<p>
 * 1 <= n == maxHeights <= 10^5<p>
 * 1 <= maxHeights[i] <= 10^9<p>
 */
public class LeetCode2866 {

    @Test
    public void test01() {
//        List<Integer> maxHeights = Arrays.asList(5, 3, 4, 1, 1);
//        List<Integer> maxHeights = Arrays.asList(6, 5, 3, 9, 2, 7);
//        List<Integer> maxHeights = Arrays.asList(3, 2, 5, 5, 2, 3);
        List<Integer> maxHeights = Arrays.asList(3, 5, 3, 5, 1, 5, 4, 4, 4);
        System.out.println(new Solution().maximumSumOfHeights(maxHeights));
    }
}

class Solution {

    List<Integer> maxHeights;

    long ans;

    int n;

    public long maximumSumOfHeights(List<Integer> maxHeights) {
        // 存在一个 i，位于 i 左右的元素都会越来越小
        this.maxHeights = maxHeights;
        n = maxHeights.size();
        ans = 0L;
        Deque<Integer> deque = new ArrayDeque<>();
        int[] left = new int[n];
        int[] right = new int[n];
        // 初始化赋值
        Arrays.fill(left, -1);
        Arrays.fill(right, n);
        for (int i = 0; i < n; i++) {
            int x = maxHeights.get(i);
            while (!deque.isEmpty() && maxHeights.get(deque.peek()) > x) {
                deque.pop();
            }
            if (!deque.isEmpty()) {
                left[i] = deque.peek();
            }
            deque.push(i);
        }
        deque.clear();
        for (int i = n - 1; i >= 0; i--) {
            int x = maxHeights.get(i);
            while (!deque.isEmpty() && maxHeights.get(deque.peek()) >= x) {
                deque.pop();
            }
            if (!deque.isEmpty()) {
                right[i] = deque.peek();
            }
            deque.push(i);
        }
        long[] f = new long[n];
        long[] g = new long[n];
        for (int i = 0; i < n; i++) {
            int x = maxHeights.get(i);
            if (i > 0 && x >= maxHeights.get(i - 1)) {
                f[i] = f[i - 1] + x;
            } else {
                int j = left[i];
                f[i] = 1L * x * (i - j) + (j >= 0 ? f[j] : 0);
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            int x = maxHeights.get(i);
            if (i < n - 1 && x >= maxHeights.get(i + 1)) {
                g[i] = g[i + 1] + x;
            } else {
                int j = right[i];
                g[i] = 1L * x * (j - i) + (j < n ? g[j] : 0);
            }
        }
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, f[i] + g[i] - maxHeights.get(i));
        }
        return ans;
    }

    /**
     * 暴力破解，超时
     *
     * @param index 高峰所在位置
     */
    public void dfs(int index) {
        long max = 0L;
        max += maxHeights.get(index);
        int left = maxHeights.get(index), right = maxHeights.get(index);
        for (int i = index - 1; i >= 0; i--) {
            if (maxHeights.get(i) <= left) {
                max += maxHeights.get(i);
                left = maxHeights.get(i);
            } else {
                max += left;
            }
        }
        for (int i = index + 1; i < n; i++) {
            if (maxHeights.get(i) <= right) {
                max += maxHeights.get(i);
                right = maxHeights.get(i);
            } else {
                max += right;
            }
        }
        ans = Math.max(max, ans);
    }
}
